/**
 * @program: 11.8
 * @description:
 * @author: 李鑫月
 * @create: 2021-11-08 19:21
 **/

/**组成：
 * 1.顺序表底层是一个数组，他是一个逻辑上和物理上都连续。
 * 2.链表是一个由若干接点组成的一个数据结构，逻辑上是连续的，物理上不一定连续。
 * 操作：
 * 顺序表随机存取，链表顺序存取
 * 1.顺序表适合查找相关的操作，可以使用下标，直接获取。
 * 2.链表适合频繁的插入和删除操作，时间复杂度低。
 *
 * 空间：
 * 顺序表的空间利用率不高。链表随用随取。
 */
class ListNode{
    public int val;
    public ListNode prev;
    public ListNode next;
    public ListNode(int val){
        this.val=val;
    }

}
public class MyLinkedlist {
    public ListNode head;
    public ListNode last;

        //头插法
        public void addFirst(int data){
            ListNode node=new ListNode(data);
            if(this.head==null){
                this.head=node;
                this.last=node;
            }else {
                node.next=this.head;
                this.head.prev=node;
                this.head=node;
            }
        }
        //尾插法
        public void addLast(int data){
            ListNode node=new ListNode(data);
            if(this.head==null){
                this.head=node;
                this.last=node;
            }
            else{
                this.last.next=node;
                node.prev=this.last;
                this.last=node;
            }

        }
        public ListNode searchIndex(int index){
            ListNode cur=this.head;
            if(index<0||index>size()){
                return null;
            }else {
                while(index!=0){
                    cur=cur.next;
                    index--;
                }
                return cur;
            }
        }
        //任意位置插入,第一个数据节点为0号下标
        public boolean addIndex(int index,int data){

            ListNode node=new ListNode(data);
            if(index==0){
                addFirst(data);
                return true;
            }
            if(index==size()){
                addLast(data);
                return true;
            }
            ListNode cur=searchIndex(index);
            if(cur==null){
                return false;
            }
            node.prev=cur.prev;
            node.next=cur;
            cur.prev.next=node;
            cur.prev=node;
            return true;
        }
        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key){
            ListNode cur=this.head;
            while(cur!=null){
                if(cur.val==key) {
                    return true;
                }
                cur=cur.next;
            }
            return false;
        }
        //得到单链表的长度
        public int size(){
            ListNode cur=this.head;
            int count=0;
            while(cur!=null){
                count++;
                cur=cur.next;
            }
            return count;
        }
        public void display(){
            ListNode cur=this.head;

            while(cur!=null){
                System.out.print(cur.val+"->");
                cur=cur.next;
            }
            System.out.println("null");

        }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
          ListNode cur=this.head;

          if(key==this.head.val){
              head=head.next;
              if(head!=null){
                  head.prev=null;
              }
              else {
                 last=null;
             }

          }else if(key==this.last.val){
              last=last.prev;
              last.next=null;
          }else {
              while (cur!=null){
                  if(cur.val==key){
                      cur.prev.next=cur.next;
                      cur.next.prev=cur.prev;
                      return;
                  }
                  cur=cur.next;
              }
              System.out.println("未找到key结点");
          }


    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        ListNode cur=this.head;

        if(key==this.head.val){
            head=head.next;
            if(head!=null){
                head.prev=null;
            }
            else {
                last=null;
            }
            return;

        }
        if(key==this.last.val){
            last=last.prev;
            last.next=null;
            return;
        }

            while (cur!=null){
                if(cur.val==key){
                    cur.prev.next=cur.next;
                    cur.next.prev=cur.prev;

                }
                cur=cur.next;
            }
            System.out.println("未找到key结点");
        }



        public void clear(){

            while (head!=null){
                ListNode Next=this.head.next;
                head.prev=null;
                head.next=null;
                head=Next;

            }
         last=null;
        }


}
